﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Xunit;

namespace Tournament_1
{
    public class Class1
    {
        [Fact]
        public void Simple()
        {
            var input = new string[] { "CLAS001:CLB123", "CLB123" };
            var expected = new string[] { "CLB123", "CLAS001" };

            AssertArrayEqual(input, expected);
        }

        [Fact]
        public void Dead()
        {
            var input = new string[] { "CLAS001:CLB123", "CLB123:CLAS001" };
            var expected = new string[] { };

            AssertArrayEqual(input, expected);
        }

        [Fact]
        public void UncompleteCondition()
        {
            var input = new string[] { "CLAS001:CLB123" };
            var expected = new string[] { };

            AssertArrayEqual(input, expected);
        }

        private static void AssertArrayEqual(string[] input, string[] expected)
        {
            var output = new Prerequirement().orderClass(input);

            Assert.Equal(expected.Length, output.Length);
            for (int i = 0; i < expected.Length; i++)
                Assert.Equal(expected[i], output[i]);
        }
    }

    class Class
    {
        public string Name { get; set; }
        public string[] Required { get; set; }

        public List<Class> RequiredClasses { get; set; }
    }

    class Prerequirement
    {
        public string[] orderClass(string[] conditions)
        {
            Dictionary<string, List<string>> requireRelationship = new Dictionary<string, List<string>>();

            foreach (string token in conditions)
            {
                int index = token.IndexOf(':');
                string name = index > 0 ? token.Substring(0, index) : token;
                string[] rquired = index > 0 ? token.Substring(index + 1).Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries) : new string[0];

                requireRelationship.Add(name, new List<string>(rquired));
            }

            try
            {
                Dictionary<string, int> classDeepth = GetDeepth(requireRelationship);
                SortedDictionary<int, SortedDictionary<int, string>> sortResult = new SortedDictionary<int, SortedDictionary<int, string>>();

                foreach (KeyValuePair<string, int> pair in classDeepth)
                {
                    SortedDictionary<int, string> xx;
                    if (!sortResult.TryGetValue(pair.Value, out xx))
                        xx = sortResult[pair.Value] = new SortedDictionary<int, string>();

                    xx.Add(int.Parse(pair.Key.Substring(pair.Key.Length - 3)), pair.Key);
                }

                List<string> result = new List<string>();

                foreach (SortedDictionary<int, string> value in sortResult.Values)
                {
                    foreach (string xxx in value.Values)
                    {
                        result.Add(xxx);
                    }
                }

                return result.ToArray();
            }
            catch (Exception)
            {
                return new string[0];
            }
        }

        private Dictionary<string, int> GetDeepth(Dictionary<string, List<string>> requireRelationship)
        {
            Dictionary<string, int> classDeepth = new Dictionary<string, int>();

            foreach (string className in requireRelationship.Keys)
            {
                calcStack = new Stack<string>();
                GetDeepth(classDeepth, requireRelationship, className);
            }

            return classDeepth;
        }
        private Stack<string> calcStack = new Stack<string>();

        private int GetDeepth(Dictionary<string, int> classDeepth, Dictionary<string, List<string>> requireRelationship, string className)
        {
            if (calcStack.Count > requireRelationship.Count)
            {
                throw new ApplicationException("cant finished.");
            }

            calcStack.Push(className);

            if (classDeepth.ContainsKey(className))
            {
                calcStack.Pop();
                return classDeepth[className];
            }
            else
            {
                List<string> requiement = requireRelationship[className];

                if (requiement.Count == 0)
                {
                    calcStack.Pop();
                    return classDeepth[className] = 0;
                }
                else
                {
                    int maxDeepth = int.MinValue;
                    foreach (string requireClass in requiement)
                    {
                        int deepth = classDeepth[requireClass] = GetDeepth(classDeepth, requireRelationship, requireClass);
                        if (deepth > maxDeepth)
                        {
                            maxDeepth = deepth;
                        }
                    }

                    calcStack.Pop();
                    return classDeepth[className] = maxDeepth + 1;
                }
            }
        }
    }

}
